/*
 * 版权所有(C)，方太互联网应用技术部，lizhixing，所有权利保留。
 * <p>
 * 项目名：	algorithm-demo
 * 文件名：	Question1481
 * 模块说明：
 * 修改历史：
 * 2025/4/25 - lizhixing - 创建。
 */
package com.lovely602.algorithm.wansuanfa;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 给你一个整数数组 arr 和一个整数 k 。现需要从数组中恰好移除 k 个元素，请找出移除后数组中不同整数的最少数目。
 * <p>
 * 示例1： 输入：arr = [5,5,4], k = 1
 * <p>
 * 输出：1
 * <p>
 * 解释：移除 1 个 4 ，数组中只剩下 5 一种整数。
 * <p>
 * 示例2： 输入：arr = [4,3,1,1,3,3,2], k = 3
 * <p>
 * 输出：2
 * <p>
 * 解释：先移除 4、2 ，然后再移除两个 1 中的任意 1 个或者三个 3 中的任意 1 个，最后剩下 1 和 3 两种整数。
 * <p>
 * 1 <= arr.length <= 10^5
 * <p>
 * 1 <= arr[i] <= 10^9
 * <p>
 * 0 <= k <= arr.length
 * <p>
 * 通过map先统计每个元素出现的频率，然后再根据频率从小到大排序，最后在移除频率最小的 k
 * 个元素即可。移除的时候要注意，最后一个元素有可能没有完全移除，比如[1,2,2,2,4,4,4,4]，k=3，我们可以移除 1 和 2 ，但 2 没有被全部移除，还剩下一个。
 *
 * @author lizhixing
 */
public class Question1481 {

  public static void main(String[] args) {
    int[] arr = { 1, 2, 2, 3, 3, 3, 4, 4, 4, 4 };
    int k = 2;
    System.out.println(new Question1481().findLeastNumOfUniqueInts(arr, k));
  }

  public int findLeastNumOfUniqueInts(int[] arr, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i : arr) {
      map.put(i, map.getOrDefault(i, 0) + 1);
    }
    List<Integer> list = new ArrayList<>(map.values());
    Collections.sort(list);
    for (int i = 0; i < list.size(); i++) {
      if (k >= list.get(i)) {
        k -= list.get(i);
        list.remove(i);
        i--;
      } else {
        break;
      }
    }
    return list.size();
  }

}
